In the fields of computer-aided design ("CAD"), computer-aided engineering ("CAE"), and computer-aided manufacturing ("CAM"), an essential technological element is "interactive computer graphics." By using this technology, the viewer of the graphic display can modify the displayed image and observe the immediate and consequential effects of such modification of the object or document displayed. In order for the aforementioned technology to be of maximum value, the image shown on the display device should be portrayed in full color.
As is well known, the most commonly-used display device is the color cathode-ray tube. Of course, the color cathode-ray tube is an analog device in which the position and intensity of each illuminated spot formed on the face of the tube by its electron beams are continuous functions of the respective voltages applied to the deflecting plates and the electron guns of the tube. Most commonly, there is one electron gun for each of three primary colors: red, green, and blue. Thus, the location of each illuminated spot on the screen is determined by the voltages on the deflecting plates, whereas the color and intensity of each illuminated spot are determined by the absolute and relative magnitudes of the voltages applied to the electron guns. The absolute magnitude of each voltage determines the intensity of illumination of the spot, whereas the relative magnitudes of the voltages on the respective electron guns determine the spectral hue of each spot.
So long as the electronic circuitry that supplies the aforementioned voltages to the deflecting plates and electron guns of the color cathode-ray tube is capable of smooth variations in output magnitude, the lines drawn on the display can likewise be smooth and free from "jaggies." Furthermore, when the control circuitry for the cathode-ray tube is strictly analog in nature, there is no limitation on the freedom of choice concerning the respective paths to be followed by lines drawn on the face of the display. When a cathode-ray tube is used in random-scan fashion, controlled by analog circuitry, a line can be drawn on the face of the tube directly from any "addressable" point to any other addressable point on the face of the tube.
By contrast, when a color cathode-ray tube is used as the output or display device of a computer-graphics apparatus, it is generally no longer possible to connect directly any two arbitrarily-chosen points on the face of the tube by a straight line having no irregularities. Thus, the display device used in computer graphics must be regarded as having a matrix of discrete picture elements, or "pixels," each of which can be activated or made bright when it is energized by an electron beam of the cathode-ray tube. Except in certain limited circumstances, it is not possible to draw a perfectly straight line from one arbitrary addressable point on the face of the tube to another arbitrary addressable point on the face of the tube. In conventional computer graphics, the best that can be achieved is an approximation of a straight line by activating a series of pixels as close as possible to the desired path of the line on the face of the tube. Only in the special cases of lines which are horizontal or vertical, or which have a slope with an absolute magnitude of unity, will the activated pixels form the desired perfectly straight line. In all other cases, the desired straight line will be only approximated by the pixels which are illuminated as closely as possible to the desired path of the line. The departure of the displayed line from the desired straight line is called "error," which includes the effects of "aliasing" characterized by a series of "stair steps," impairing the best possible approximation of a smoothly-sloping line on the face of the cathode-ray tube. Those "stair steps" become especially apparent, and consequently most offensive, in lines which are very close to the vertical or very close to the horizontal directions on the tube face. The "stair steps" disappear when the line has a slope of unity or when it is absolutely horizontal or vertical in its direction of orientation.
In computer graphics, the electronic circuitry that assembles the data for determining the location, intensity, and color of each illuminated spot on the face of the cathode-ray tube is digital, rather than analog, in nature. Only in the very last stage prior to inputting the voltages to the control electrodes of the cathode-ray tube are those voltages converted from digital to analog form. In most computer display apparatus, an electronic representation of each and every pixel of the display is "mapped" in a large piece of contiguous memory hardware called a "frame-buffer pixel memory." For each pixel desired to be displayed on the face of the cathode-ray tube, there must be in the frame-buffer pixel memory an address at which sufficient data are stored to specify the color intensity and hue of that pixel in the display. Assuming that the "rasterized image" desired to be displayed covers the entire face of the cathode-ray tube, there must be in the frame-buffer pixel memory a data entry for each pixel on the face of the tube. The sum total of this memory is called a "bit plane." If the display device were a black-and-white, or monochrome, cathode-ray tube, the entry of a single bit of intensity data at each address in the frame-buffer pixel memory would suffice. However, since it is our assumption that we are interested primarily in a display apparatus having multi-color capabilities, a plurality of bit planes is required. Thus, in the type of apparatus with which this invention is concerned, the frame-buffer pixel memory assembles data constituting a plurality of bit planes. One bit of data can be stored in each such bit plane at a time.
Each of the pixels to be displayed on the face of the cathode-ray tube must have an address at which its color intensity and hue are stored in the frame-buffer pixel memory. Each such address is commonly stated in terms of the X and Y Cartesian coordinates of the pixel to be activated on the face of the cathode-tray tube. Assuming that a straight line is desired to be plotted for display on the screen, the computation of the successive X and Y coordinates of the respective pixels approximating such a straight line has often been carried out by incrementing or decrementing either the X or Y coordinate of a pixel address by one unit and by determining a "delta value" by which the other coordinate must be adjusted to correspond to the unit incrementation or decrementation of the first-mentioned coordinate in going from the address of one pixel to the address of the next pixel to be plotted and displayed. If the absolute magnitude of the slope of the line to be drawn is less than unity, such a prior-art line-drawing apparatus would increment the X coordinate by one unit and then compute the delta value for the Y coordinate, which would be an amount less than unity. On the other hand, if the absolute magnitude of the slope of the line to be drawn is greater than unity, the apparatus would increment the Y coordinate by one unit and then compute the delta value for the X coordinate which, again, would be an amount less than unity. If the slope of the line to be drawn is negative, or if it is being plotted from right to left, incrementation is replaced by decrementation. In order to avoid cumbersome repetition, the word "increment" will be used in the remainder of this specification to include both "increment" and "decrement."
According to a commonly-used prior-art algorithm developed for this purpose by J.E. Bresenham and published in an article entitled, "Algorithm for Computer Control of a Digital Plotter," appearing in the IBM System Journal, Vol. 4, pp. 25-30 in 1965, the "error" had to be evaluated during each iteration of the operative "loop" of the algorithm. The error to be evaluated was the "departure" or distance of each plotted pixel from the line desired to be plotted. This "condition testing" and "branching" in each loop of the algorithm were very expensive in terms of processing time. Moreover, the inability of prior-art microprocessors to handle numbers in other than "integer format" made infeasible the processing or computation of pixel addresses in non-integer format that might have permitted significant time savings to be made. Furthermore, the prior art has been deficient in that no satisfactory means was provided for the elimination of the offensive "jaggies" appearing in most lines of displays using prior-art apparatus and prior-art processing methods.